<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 6.0.0">
  <link rel="apple-touch-icon" sizes="180x180" href="/wang-cheng/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/wang-cheng/images/favicon-32x32-next.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/wang-cheng/images/favicon-16x16-next.png">
  <link rel="mask-icon" href="/wang-cheng/images/logo.svg" color="#222">

<link rel="stylesheet" href="/wang-cheng/css/main.css">


<link rel="stylesheet" href="/wang-cheng/lib/font-awesome/css/all.min.css">

<script id="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"cheng-wang123.gitee.io","root":"/wang-cheng/","scheme":"Gemini","version":"7.8.0","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12,"onmobile":false},"copycode":{"enable":false,"show_result":false,"style":null},"back2top":{"enable":true,"sidebar":false,"scrollpercent":false},"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"algolia":{"hits":{"per_page":10},"labels":{"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}},"localsearch":{"enable":false,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}}};
  </script>

  <meta name="description" content="贪心算法在某一个标准下，优先考虑最满足标准的样本，最后考虑最不满足标准的样本，最终得到一个答案的算法，叫做贪心算法。 也就是说，不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解  一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。给你每一个项目开始的时间和结束的时间(给你一个数组，里面是一个个具体的项目)，你来安排宣讲的日程，要求会议室进行的宣讲的场次最多。返回这个最多的宣">
<meta property="og:type" content="article">
<meta property="og:title" content="算法笔记(三)">
<meta property="og:url" content="https://cheng-wang123.gitee.io/wang-cheng/2022/04/02/%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0-%E4%B8%89/index.html">
<meta property="og:site_name" content="诚の博客">
<meta property="og:description" content="贪心算法在某一个标准下，优先考虑最满足标准的样本，最后考虑最不满足标准的样本，最终得到一个答案的算法，叫做贪心算法。 也就是说，不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解  一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。给你每一个项目开始的时间和结束的时间(给你一个数组，里面是一个个具体的项目)，你来安排宣讲的日程，要求会议室进行的宣讲的场次最多。返回这个最多的宣">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="2022-04-02T02:01:00.000Z">
<meta property="article:modified_time" content="2022-04-03T02:47:12.636Z">
<meta property="article:author" content="王诚">
<meta property="article:tag" content="左神">
<meta name="twitter:card" content="summary">

<link rel="canonical" href="https://cheng-wang123.gitee.io/wang-cheng/2022/04/02/%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0-%E4%B8%89/">


<script id="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true,
    lang   : 'zh-CN'
  };
</script>

  <title>算法笔记(三) | 诚の博客</title>
  






  <noscript>
  <style>
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript>

<link rel="alternate" href="/wang-cheng/atom.xml" title="诚の博客" type="application/atom+xml">
</head>

<body itemscope itemtype="http://schema.org/WebPage">
  <div class="container use-motion">
    <div class="headband"></div>

    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏">
      <span class="toggle-line toggle-line-first"></span>
      <span class="toggle-line toggle-line-middle"></span>
      <span class="toggle-line toggle-line-last"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/wang-cheng/" class="brand" rel="start">
      <span class="logo-line-before"><i></i></span>
      <h1 class="site-title">诚の博客</h1>
      <span class="logo-line-after"><i></i></span>
    </a>
      <p class="site-subtitle" itemprop="description">记录学习中的点点滴滴</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
    </div>
  </div>
</div>




<nav class="site-nav">
  <ul id="menu" class="main-menu menu">
        <li class="menu-item menu-item-home">

    <a href="/wang-cheng/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a>

  </li>
        <li class="menu-item menu-item-tags">

    <a href="/wang-cheng/tags/" rel="section"><i class="fa fa-tags fa-fw"></i>标签</a>

  </li>
        <li class="menu-item menu-item-categories">

    <a href="/wang-cheng/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类</a>

  </li>
        <li class="menu-item menu-item-archives">

    <a href="/wang-cheng/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档</a>

  </li>
  </ul>
</nav>




</div>
    </header>

    
  <div class="back-to-top">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>


    <main class="main">
      <div class="main-inner">
        <div class="content-wrap">
          

          <div class="content post posts-expand">
            

    
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="https://cheng-wang123.gitee.io/wang-cheng/2022/04/02/%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0-%E4%B8%89/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/wang-cheng/images/avatar.gif">
      <meta itemprop="name" content="王诚">
      <meta itemprop="description" content="命运对勇士低语，你无法抵御风暴；勇士低声回应，我就是风暴">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="诚の博客">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          算法笔记(三)
        </h1>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-calendar"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>

              <time title="创建时间：2022-04-02 10:01:00" itemprop="dateCreated datePublished" datetime="2022-04-02T10:01:00+08:00">2022-04-02</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="far fa-calendar-check"></i>
                </span>
                <span class="post-meta-item-text">更新于</span>
                <time title="修改时间：2022-04-03 10:47:12" itemprop="dateModified" datetime="2022-04-03T10:47:12+08:00">2022-04-03</time>
              </span>

          
            <span class="post-meta-item" title="阅读次数" id="busuanzi_container_page_pv" style="display: none;">
              <span class="post-meta-item-icon">
                <i class="fa fa-eye"></i>
              </span>
              <span class="post-meta-item-text">阅读次数：</span>
              <span id="busuanzi_value_page_pv"></span>
            </span>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
        <h1 id="贪心算法"><a href="#贪心算法" class="headerlink" title="贪心算法"></a><strong>贪心算法</strong></h1><p>在某一个标准下，优先考虑最满足标准的样本，最后考虑最不满足标准的样本，最终得到一个答案的算法，叫做贪心算法。</p>
<p>也就是说，不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解</p>
<hr>
<p>一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。给你每一个项目开始的时间和结束的时间(给你一个数组，里面是一个个具体的项目)，你来安排宣讲的日程，要求会议室进行的宣讲的场次最多。返回这个最多的宣讲场次。</p>
<figure class="highlight arduino"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="type">static</span> <span class="keyword">class</span> <span class="title class_">Progarm</span>&#123;</span><br><span class="line">    <span class="keyword">public</span> <span class="type">int</span> start;</span><br><span class="line">    <span class="keyword">public</span> <span class="type">int</span> end;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">Program</span><span class="params">(<span class="type">int</span> start,<span class="type">int</span> end)</span></span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.start = start;</span><br><span class="line">        <span class="keyword">this</span>.end = end;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="type">static</span> <span class="keyword">class</span> <span class="title class_">ProgramComparator</span> implements Comparator&lt;Progarm&gt;&#123;</span><br><span class="line">    @<span class="function">Override</span></span><br><span class="line"><span class="function">    <span class="keyword">public</span> <span class="type">int</span> <span class="title">compare</span><span class="params">(Program o1,Program o2)</span></span>&#123;</span><br><span class="line">        <span class="keyword">return</span> o1.end - o2.end;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">//timePoint是会议室开始营业时间</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="type">static</span> <span class="type">int</span> <span class="title">bestArrange</span><span class="params">(Progarm[] progarms,<span class="type">int</span> timePoint)</span></span>&#123;</span><br><span class="line">    <span class="comment">//按照结束时间早的进行排序</span></span><br><span class="line">    Arrays.<span class="built_in">sort</span>(programs,<span class="keyword">new</span> <span class="built_in">ProgramComparator</span>());</span><br><span class="line">    <span class="type">int</span> result = <span class="number">0</span>;</span><br><span class="line">    <span class="comment">//从左往右依次遍历所有会议</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; program.length;i++)&#123;</span><br><span class="line">        <span class="keyword">if</span>(timePoint &lt;= programs[i].start)&#123;</span><br><span class="line">            result++;</span><br><span class="line">            timePoint = programs[i].end;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> result;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="贪心算法在笔试的时候的解题思路"><a href="#贪心算法在笔试的时候的解题思路" class="headerlink" title="贪心算法在笔试的时候的解题思路"></a><strong>贪心算法在笔试的时候的解题思路</strong></h3><ol>
<li><p>实现一个不依靠贪心策略的解法X，可以用最暴力(写的多了会发现暴力解法是可以复用的)的尝试</p>
</li>
<li><p>脑补出贪心策略A、贪心策略B、贪心策略C…</p>
</li>
<li><p>用解法X和对数器，去验证每一个贪心策略，用实验的方式得知哪个贪心策略正确</p>
</li>
<li><p>不要纠结贪心策略的证明</p>
</li>
</ol>
<p>贪心算法不太好准备，因为业务不同，贪心思想也不同。需要自己去练习，累计经验。<strong>但也得要写模板，写对数器的模板。</strong></p>
<p>贪心算法一般出现在笔试题当中，出现的概率挺大，但篇幅不大，频率平均是5个算法题出现一个贪心算法类型。</p>
<p>但是贪心算法出现在面试中是比较少见的，因为一个是贪心算法的代码非常短，没有办法考coding。第二个是贪心算法的题目是0&#x2F;1的问题，要么找对贪心策略要么找错贪心策略，不存在什么优化技巧之类的，所以区分度不是很高。如果面试官想要淘汰掉一部分人可能出贪心算法，但为了区分度的话不会出这种题。</p>
<hr>
<h2 id="PriorityQueue的使用"><a href="#PriorityQueue的使用" class="headerlink" title="PriorityQueue的使用"></a><strong>PriorityQueue的使用</strong></h2><p>基于优先级堆的无限优先级queue 。 优先级队列的元素根据它们的有序natural ordering ，或由一个Comparator在队列构造的时候提供，这取决于所使用的构造方法。 优先队列不允许null元素。 依靠自然排序的优先级队列也不允许插入不可比较的对象（这样做可能导致ClassCastException ）。 </p>
<p>PriorityQueue():创建一个PriorityQueue ，具有默认的初始容量（11），根据它们的natural ordering对其元素进行排序。</p>
<p>PriorityQueue(Collection&lt;? extends E&gt; c):创建一个 PriorityQueue集合中的元素的PriorityQueue。</p>
<p>PriorityQueue(Comparator&lt;? super E&gt; comparator):创建具有默认初始容量的PriorityQueue，并根据指定的比较器对其元素进行排序。</p>
<p>方法摘要：</p>
<p>boolean add(E e)  将指定的元素插入到此优先级队列中。 </p>
<p>void clear()  从此优先级队列中删除所有元素。 </p>
<p>boolean contains(Object o)  如果此队列包含指定的元素，则返回 true 。</p>
<p>Iterator<E> iterator()  返回此队列中的元素的迭代器。 </E></p>
<p>boolean offer(E e)  将指定的元素插入到此优先级队列中。 </p>
<p>E peek()  检索但不删除此队列的头，如果此队列为空，则返回 null。</p>
<p>E poll()  检索并删除此队列的头，如果此队列为空，则返回 null 。 </p>
<p>int size()  返回此集合中的元素数。 </p>
<p>Object[] toArray()  返回一个包含此队列中所有元素的数组。</p>
<hr>
<p>输入：</p>
<p>正数数组costs、正数数组profits、正数K、正数m。</p>
<p>含义：</p>
<p>costs[i]表示i号项目的花费</p>
<p>profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)</p>
<p>K表示你只能串行的最多做K个项目</p>
<p>m表示你的初始资金</p>
<p>说明:你每做完一个项目，马上获得利润，可以支持你去做下一个项目。输出：你最后获得的最大钱数</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">class</span> <span class="title class_">MinCostComparator</span> <span class="keyword">implements</span> <span class="title class_">Comparator</span>&lt;Node&gt;&#123;</span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="keyword">public</span> <span class="type">int</span> <span class="title function_">compare</span><span class="params">(Node o1,Node o2)</span>&#123;</span><br><span class="line">        <span class="keyword">return</span> o1.c - o2.c;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">class</span> <span class="title class_">MaxProfitComparator</span> <span class="keyword">implements</span> <span class="title class_">Comparator</span>&lt;Node&gt;&#123;</span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="keyword">public</span> <span class="type">int</span> <span class="title function_">compare</span><span class="params">(Node o1,Node o2)</span>&#123;</span><br><span class="line">        <span class="keyword">return</span> o2.p - o1.p;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">findMaximizedCapital</span><span class="params">(<span class="type">int</span> k,<span class="type">int</span> w,<span class="type">int</span>[] Profits,<span class="type">int</span>[] Capital)</span>&#123;</span><br><span class="line">    PriorityQueue&lt;Node&gt; minCostQ = <span class="keyword">new</span> <span class="title class_">PriorityQueue</span>&lt;Node&gt;(<span class="keyword">new</span> <span class="title class_">MinCostComparator</span>);</span><br><span class="line">    PriorityQueue&lt;Node&gt; maxProfitQ = <span class="keyword">new</span> <span class="title class_">PriorityQueue</span>&lt;&gt;(<span class="keyword">new</span> <span class="title class_">MaxProfitComparator</span>);</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; Profits.length;i++)&#123;</span><br><span class="line">        minCostQ.add(<span class="keyword">new</span> <span class="title class_">Node</span>(Profits[i],Capital[i]));</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>;i &lt; K;i++)&#123;</span><br><span class="line">        <span class="keyword">while</span>(!minCostQ.isEmpty() &amp;&amp; minCostQ.peek().c &lt;= w)&#123;</span><br><span class="line">            maxProfitQ.add(minCostQ.poll());</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span>(maxProfitQ.isEmpty())&#123;</span><br><span class="line">            <span class="keyword">return</span> w;</span><br><span class="line">        &#125;</span><br><span class="line">        w += maxProfitQ.poll().p;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> w;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>


<p>额外插入一个堆的题目：</p>
<p>一个数据流中，随时可以取得中位数</p>
<p>准备一个大根堆和小根堆</p>
<ol>
<li><p>给的第一个数字直接入大根堆</p>
</li>
<li><p>再获得一个数，判断当前获得的数是否小于大根堆的堆顶元素</p>
</li>
<li><p>如果是，当前元素入大根堆，如果不是，当前元素入小根堆</p>
</li>
<li><p>每次循环都判断两个堆的大小，如果两者大小相差2，那么较大的那个堆的堆顶弹出进较小的那个堆的堆顶</p>
</li>
</ol>
<h2 id="N皇后问题"><a href="#N皇后问题" class="headerlink" title="N皇后问题"></a><strong>N皇后问题</strong></h2><p>N皇后问题是指在N*N的棋盘上要摆N个皇后，要求任何两个皇后不同行、不同列，也不在同一条斜线上</p>
<p>给定一个整数n，返回N皇后的摆法有多少种。</p>
<p>n&#x3D;1，返回1</p>
<p>n&#x3D;2或3，2皇后和3皇后问题无论怎么摆放都不行，返回0。</p>
<p>n&#x3D;8，返回92</p>
<figure class="highlight pgsql"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br></pre></td><td class="code"><pre><span class="line"><span class="built_in">public</span> static <span class="type">int</span> num1(<span class="type">int</span> n)&#123;</span><br><span class="line">    <span class="keyword">if</span>(n &lt; <span class="number">1</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="type">int</span>[] <span class="type">record</span> = <span class="built_in">new</span> <span class="type">int</span>[n];//用一个单数组表示   <span class="type">record</span>[i] = j 表示i行j列处放皇后</span><br><span class="line">    <span class="keyword">return</span> process1(<span class="number">0</span>,<span class="type">record</span>,n);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">//i表示现在来到了第几行</span><br><span class="line">//n表示整体一共多少行</span><br><span class="line">//返回值是，摆完所有的皇后，合理的摆法有多少种</span><br><span class="line"><span class="built_in">public</span> static <span class="type">int</span> process1(<span class="type">int</span> i,<span class="type">int</span>[] <span class="type">record</span>,<span class="type">int</span> n)&#123;</span><br><span class="line">    <span class="keyword">if</span>(i == n)&#123;//i = n 是终止行，n是n行n列的下一行，不属于<span class="type">record</span>数组，如果能执行这条语句，就证明前面行摆的都符合了条件，那么也就代表着我找到了一种摆法。</span><br><span class="line">        <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="type">int</span> res = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">0</span>;j &lt; n; j++)&#123;//当前行在i行，尝试i行所有的列 <span class="comment">--&gt; j</span></span><br><span class="line">        //当前i行的皇后，放在j列，会不会和之前(<span class="number">0.</span>..i<span class="number">-1</span>)的皇后，共行共列或者共斜线</span><br><span class="line">        //如果是，认为有效</span><br><span class="line">        //如果不是，认为无效</span><br><span class="line">        <span class="keyword">if</span>(isValid(<span class="type">record</span>,i,j))&#123;</span><br><span class="line">            <span class="type">record</span>[i] = j;</span><br><span class="line">            res += process1(i+<span class="number">1</span>,<span class="type">record</span>,n);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br><span class="line"><span class="built_in">public</span> static <span class="type">boolean</span> isValid(<span class="type">int</span>[] <span class="type">record</span>,<span class="type">int</span> i,<span class="type">int</span> j)&#123;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> k = <span class="number">0</span>; k &lt; i; k++)&#123;</span><br><span class="line">        <span class="keyword">if</span>(j == <span class="type">record</span>[k] || Math.abs(<span class="type">record</span>[k]-j) == Math.abs(i-k))&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>N皇后问题的时间复杂度为O(N^N)，该指标已经没有办法优化，已经是最优解。<strong>但常数部分还可以优化，而且优化的方式有多种</strong></p>
<p>这里演示的这种优化方式，就是利用位运算的特性，代替record的检查</p>
<figure class="highlight hsp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br></pre></td><td class="code"><pre><span class="line">public static <span class="keyword">int</span> num2(<span class="keyword">int</span> n)&#123;</span><br><span class="line">    <span class="keyword">if</span>(n &lt;<span class="number">1</span> || n&gt; <span class="number">32</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span><span class="comment">;</span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//该行表示将一个32位的数，n皇后问题，后面n个1，前面全部为0。这个数不代表任何信息，只使用这个数的位信息</span></span><br><span class="line">    <span class="comment">//例如n为8，00000000000000000000000011111111</span></span><br><span class="line">    <span class="keyword">int</span> <span class="keyword">limit</span> = n == <span class="number">32</span> ? <span class="number">-1</span> : (<span class="number">1</span> &lt;&lt; n) <span class="number">-1</span><span class="comment">;</span></span><br><span class="line">    <span class="comment">//在limit限制的范围内，一开始我行、斜线都没限制的情况下，有多少种</span></span><br><span class="line">    <span class="keyword">return</span> process2(<span class="keyword">limit</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>)<span class="comment">;</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="comment">//limit是做限制用的，通过前面的运算已经得出limit的后n位是1了，那么下面的函数就被限制在是1的范围内去尝试了</span></span><br><span class="line"><span class="comment">//leftDiaLim 左斜线的限制，1的位置不能放皇后，0的位置可以</span></span><br><span class="line"><span class="comment">//rightDiaLim 右斜线的限制，1的位置不能放皇后，0的位置可以</span></span><br><span class="line">public static <span class="keyword">int</span> process2(<span class="keyword">int</span> <span class="keyword">limit</span>,<span class="keyword">int</span> colLim,<span class="keyword">int</span> leftDiaLim, <span class="keyword">int</span> rightDiaLim)&#123;</span><br><span class="line">    <span class="keyword">if</span>(colLim == <span class="keyword">limit</span>)&#123; <span class="comment">//当列上的限制和limit一样了，代表所有位置都被限制了，这时候代表找到了一种放置</span></span><br><span class="line">        <span class="keyword">return</span> <span class="number">1</span><span class="comment">;</span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> <span class="keyword">pos</span> = <span class="number">0</span><span class="comment">;</span></span><br><span class="line">    <span class="keyword">int</span> mostRightOne = <span class="number">0</span><span class="comment">;</span></span><br><span class="line"></span><br><span class="line">    <span class="comment">//列的限制 | 左对角线的限制 | 右对角线的限制 = 总限制 (1代表能放皇后，0代表不可以放皇后)</span></span><br><span class="line">    <span class="comment">// 与limit进行与操作后，会将pos 的前32-n位数全部置为0，这样这些0就是不可以选皇后的位置，也就限制了选皇后的范围</span></span><br><span class="line">    <span class="keyword">pos</span> = <span class="keyword">limit</span> &amp; (~(colLim | leftDiaLim | rightDiaLim))<span class="comment">;</span></span><br><span class="line">    </span><br><span class="line">    </span><br><span class="line">    <span class="keyword">int</span> res = <span class="number">0</span><span class="comment">;</span></span><br><span class="line">    <span class="keyword">while</span>(<span class="keyword">pos</span> != <span class="number">0</span>)&#123;</span><br><span class="line">        <span class="comment">//pos &amp; (~pos + 1)   把一个二进制的数，最右侧的1提取出来</span></span><br><span class="line">        <span class="comment">//提取出候选皇后位置状态中最右侧的依赖</span></span><br><span class="line">        <span class="comment">//因为只有为1的位置上才可以放皇后，所以这条语句是找出最右侧的1，然后提取出来。</span></span><br><span class="line">        mostRightOne = <span class="keyword">pos</span> &amp; (~<span class="keyword">pos</span> + <span class="number">1</span>)<span class="comment">;</span></span><br><span class="line">        <span class="comment">//这里将最右侧的1剪掉，也就是将这个1改为0</span></span><br><span class="line">        <span class="keyword">pos</span> = <span class="keyword">pos</span> - mostRightOne<span class="comment">;</span></span><br><span class="line">        <span class="comment">//limit不变</span></span><br><span class="line">        <span class="comment">//因为我在mostRightOne的位置放了皇后，所以接下来列的限制为colLim | mostRightOne的形式。</span></span><br><span class="line">        <span class="comment">//因为我在mostRightOne的位置放了皇后，所以接下来左斜线的限制为leftDiaLim | mostRightOne 完成后往左移一位</span></span><br><span class="line">        <span class="comment">//因为我在mostRightOne的位置放了皇后，所以接下来右斜线的限制为rightDiaLim | mostRightOne 完成后往右移一位</span></span><br><span class="line">        <span class="comment">//res 累加每种尝试，返回</span></span><br><span class="line">        res += process2(<span class="keyword">limit</span>,colLim | mostRightOne,(leftDiaLim | mostRightOne) &lt;&lt; <span class="number">1</span>,(rightDiaLim | mostRightOne) &gt;&gt;&gt; <span class="number">1</span>)<span class="comment">;</span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res<span class="comment">;</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="暴力递归"><a href="#暴力递归" class="headerlink" title="暴力递归"></a><strong>暴力递归</strong></h2><ol>
<li><p>把问题转化为规模缩小了的同类问题的子问题</p>
</li>
<li><p>有明确的不需要继续进行递归的条件</p>
</li>
<li><p>有当得到了子问题的结果之后的决策过程</p>
</li>
<li><p>不记录每一个子问题的解</p>
</li>
</ol>
<h3 id="汉诺塔问题"><a href="#汉诺塔问题" class="headerlink" title="汉诺塔问题"></a><strong>汉诺塔问题</strong></h3><p>打印n层汉诺塔从最左边移动到最右边的全部过程</p>
<p>一般新手可能会弄不清楚怎么保证i-1在从start移动到other的过程中和从other移动到end的过程中，大圆盘一定在下面</p>
<p>其实这是从全局来考虑整个过程。其实递归算法并不需要全局考虑，只需要保证你拆分的每一步(整个过程可以被拆分成相类似的局部过程)都符合要求，那么整体也一定符合要求。</p>
<figure class="highlight pgsql"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="built_in">public</span> static <span class="type">void</span> hanoi(<span class="type">int</span> n)&#123;</span><br><span class="line">    <span class="keyword">if</span>(n &gt; <span class="number">0</span>)&#123;</span><br><span class="line">        func(n,&quot;左&quot;,&quot;中&quot;,&quot;右&quot;);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="built_in">public</span> static <span class="type">void</span> func(<span class="type">int</span> i,String <span class="keyword">start</span>,String <span class="keyword">end</span>,String other)&#123;</span><br><span class="line">    <span class="keyword">if</span>(i == <span class="number">1</span>)&#123;</span><br><span class="line">        <span class="keyword">System</span>.<span class="keyword">out</span>.println(&quot;Move 1 from &quot; + <span class="keyword">start</span> + &quot;to&quot; + <span class="keyword">end</span>);</span><br><span class="line">    &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">        func(i<span class="number">-1</span>,<span class="keyword">start</span>,other,<span class="keyword">end</span>);</span><br><span class="line">        <span class="keyword">System</span>.<span class="keyword">out</span>.println(&quot;Move &quot; +  i + &quot;from &quot; + <span class="keyword">start</span> + &quot;to&quot; + <span class="keyword">end</span>);</span><br><span class="line">        func(i<span class="number">-1</span>,other,<span class="keyword">end</span>,<span class="keyword">start</span>);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="打印一个字串的全部子序列，包括空字符串"><a href="#打印一个字串的全部子序列，包括空字符串" class="headerlink" title="打印一个字串的全部子序列，包括空字符串"></a><strong>打印一个字串的全部子序列，包括空字符串</strong></h3><figure class="highlight csharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//当前来到i位置，要和不要，走两条路</span></span><br><span class="line"><span class="comment">//res之前的选择，所形成的列表</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">process</span>(<span class="params"><span class="built_in">char</span>[] str,<span class="built_in">int</span> i,List&lt;Character&gt; res</span>)</span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span>(i == str.length)&#123;</span><br><span class="line">        <span class="comment">//打印列表</span></span><br><span class="line">        printList(res);</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    List&lt;Character&gt; resKeep = copyList(res);</span><br><span class="line">    resKeep.<span class="keyword">add</span>(str[i]);</span><br><span class="line">    process(str,i+<span class="number">1</span>,resKeep);<span class="comment">//要当前字符的路</span></span><br><span class="line">    List&lt;Character&gt; resNoInclude = copyList(res);</span><br><span class="line">    process(str,i+<span class="number">1</span>,resNoInclude);<span class="comment">//不要当前字符的路</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">printList</span>(<span class="params">List&lt;Character&gt; res</span>)</span>&#123;</span><br><span class="line">    <span class="comment">//...</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> List&lt;Character&gt; <span class="title">copyList</span>(<span class="params">List&lt;Character&gt; list</span>)</span>&#123;</span><br><span class="line">    <span class="comment">//...</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//省空间的做法，通过chs空间的复用实现</span></span><br><span class="line"><span class="comment">//当前来到i位置，要和不要，走两条路</span></span><br><span class="line"><span class="comment">//之前的选择，所形成的结果，是str</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">process</span>(<span class="params"><span class="built_in">char</span>[] chs,<span class="built_in">int</span> i</span>)</span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(i == chs.length)&#123;</span><br><span class="line">        System.<span class="keyword">out</span>.println(String.valueOf(chs));</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    process(chs,i+<span class="number">1</span>);<span class="comment">//要当前字符的路</span></span><br><span class="line">    <span class="built_in">char</span> temp = chs[i];</span><br><span class="line">    chs[i] = <span class="number">0</span>;</span><br><span class="line">    process(chs,i+<span class="number">1</span>);<span class="comment">//不要当前字符的路</span></span><br><span class="line">    chs[i] = temp;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="打印一个字符串的全部排列"><a href="#打印一个字符串的全部排列" class="headerlink" title="打印一个字符串的全部排列"></a><strong>打印一个字符串的全部排列</strong></h3><p>打印一个字符串的全部排列，要求不要出现重复的排列</p>
<figure class="highlight processing"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="built_in">ArrayList</span>&lt;<span class="built_in">String</span>&gt; <span class="title function_">Permutation</span>(<span class="built_in">String</span> <span class="built_in">str</span>)&#123;</span><br><span class="line">    <span class="built_in">ArrayList</span>&lt;<span class="built_in">String</span>&gt; res = <span class="keyword">new </span><span class="class title_">ArrayList</span>&lt;&gt;();</span><br><span class="line">    <span class="keyword">if</span>(<span class="built_in">str</span> == <span class="literal">null</span> || <span class="built_in">str</span>.<span class="property">length</span>() == <span class="number">0</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> res;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="type">char</span>[] chs = <span class="built_in">str</span>.<span class="property">toCharArray</span>();</span><br><span class="line">    <span class="title function_">process</span>(chs,<span class="number">0</span>,res);</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">process</span>(<span class="type">char</span>[] <span class="built_in">str</span>,<span class="type">int</span> i,<span class="built_in">ArrayList</span>&lt;<span class="built_in">String</span>&gt; res)&#123;</span><br><span class="line">    <span class="keyword">if</span>(i == <span class="built_in">str</span>.<span class="property">length</span>)&#123;</span><br><span class="line">        res.<span class="property">add</span>(<span class="built_in">String</span>.<span class="property">valueOf</span>(<span class="built_in">str</span>));</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="type">boolean</span>[] visit = <span class="keyword">new </span><span class="class title_">boolean</span>[<span class="number">26</span>];<span class="comment">//用于去重</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> j = i; j&lt; <span class="built_in">str</span>; j++)&#123;</span><br><span class="line">        <span class="keyword">if</span>(!visit[<span class="built_in">str</span>[j] - <span class="string">&#x27;a&#x27;</span>])&#123;<span class="comment">//如果当前试过，那么就不再试了</span></span><br><span class="line">            <span class="title function_">swap</span>(<span class="built_in">str</span>,i,j);</span><br><span class="line">            <span class="title function_">process</span>(<span class="built_in">str</span>,i+<span class="number">1</span>,res);</span><br><span class="line">            <span class="title function_">swap</span>(<span class="built_in">str</span>,i,j);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">swap</span>(<span class="type">char</span>[] chs,<span class="type">int</span> i,<span class="type">int</span> j)&#123;</span><br><span class="line">    <span class="type">char</span> temp =chs[i];</span><br><span class="line">    chs[i] = chs[j];</span><br><span class="line">    chs[j] = temp;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="纸牌的先手后手拿问题"><a href="#纸牌的先手后手拿问题" class="headerlink" title="纸牌的先手后手拿问题"></a><strong>纸牌的先手后手拿问题</strong></h2><p>有一副纸牌 [10,20,5,9,100,70,46,35,24],两个人只能从最左边或者最右边拿纸牌，一个先手拿牌一个后手拿牌，最后谁手中的牌的总和大谁赢</p>
<figure class="highlight scss"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line">public static int <span class="built_in">win1</span>(int[] arr)&#123;</span><br><span class="line">    <span class="built_in">if</span>(arr == null || arr.length == <span class="number">0</span>)&#123;</span><br><span class="line">        return <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    return Math<span class="selector-class">.max</span>(f(arr,<span class="number">0</span>,arr.length-<span class="number">1</span>),<span class="built_in">s</span>(arr,<span class="number">0</span>,arr.length-<span class="number">1</span>));</span><br><span class="line">&#125;</span><br><span class="line">public static int <span class="built_in">f</span>(int[] arr,int i,int j)&#123;</span><br><span class="line">    <span class="built_in">if</span>(i == j)&#123;</span><br><span class="line">        return arr<span class="selector-attr">[i]</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    return Math<span class="selector-class">.max</span>(arr[i] + s(arr,i+<span class="number">1</span>,j),arr<span class="selector-attr">[j]</span> + <span class="built_in">s</span>(arr,i,j-<span class="number">1</span>));</span><br><span class="line">&#125;</span><br><span class="line">public static int <span class="built_in">s</span>(int[] arr,int i,int j)&#123;</span><br><span class="line">    <span class="built_in">if</span>(i == j)&#123;</span><br><span class="line">        return <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    return Math<span class="selector-class">.min</span>(f(arr,i+<span class="number">1</span>,j),<span class="built_in">f</span>(arr,i,j-<span class="number">1</span>));</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="给你一个栈，请你逆序这个栈，不能申请额外的数据结构，只能使用递归函数。如何实现。"><a href="#给你一个栈，请你逆序这个栈，不能申请额外的数据结构，只能使用递归函数。如何实现。" class="headerlink" title="给你一个栈，请你逆序这个栈，不能申请额外的数据结构，只能使用递归函数。如何实现。"></a><strong>给你一个栈，请你逆序这个栈，不能申请额外的数据结构，只能使用递归函数。如何实现。</strong></h2><figure class="highlight axapta"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="built_in">int</span> process(<span class="built_in">char</span>[] <span class="built_in">str</span>,<span class="built_in">int</span> i)&#123;</span><br><span class="line">    <span class="keyword">if</span>(i == <span class="built_in">str</span>.length)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(<span class="built_in">str</span>[i] == <span class="string">&#x27;0&#x27;</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(<span class="built_in">str</span>[i] == <span class="string">&#x27;1&#x27;</span>)&#123;</span><br><span class="line">        <span class="built_in">int</span> res = process(<span class="built_in">str</span>,i + <span class="number">1</span>); <span class="comment">// i 自己作为单独的部分，后续有多少种方法</span></span><br><span class="line">        <span class="keyword">if</span>(i + <span class="number">1</span> &lt; <span class="built_in">str</span>.length)&#123;</span><br><span class="line">            res += process(<span class="built_in">str</span>,i+<span class="number">2</span>); <span class="comment">// (i和i+1)作为单独的部分，后续有多少种方法</span></span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> res;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(<span class="built_in">str</span>[i] == <span class="string">&#x27;2&#x27;</span>)&#123;</span><br><span class="line">        <span class="built_in">int</span> res = process(<span class="built_in">str</span>,i + <span class="number">1</span>); <span class="comment">//i自己作为单独的部分，后续有多少种方法</span></span><br><span class="line">        <span class="keyword">if</span>(i + <span class="number">1</span> &lt; <span class="built_in">str</span>.length &amp;&amp; (<span class="built_in">str</span>[i+<span class="number">1</span>] &gt;= <span class="string">&#x27;0&#x27;</span> &amp;&amp; <span class="built_in">str</span>[i + <span class="number">1</span>] &lt; = <span class="string">&#x27;6&#x27;</span>))&#123; </span><br><span class="line">            <span class="comment">//(i和i+1)作为单独的部分并且没有超过26，后续有多少种方法</span></span><br><span class="line">            res += process(<span class="built_in">str</span>,i + <span class="number">2</span>); </span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> res;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// str[i] == &#x27;3&#x27;~&#x27;9&#x27;</span></span><br><span class="line">    <span class="keyword">return</span> process(<span class="built_in">str</span>,i+<span class="number">1</span>);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="01背包问题"><a href="#01背包问题" class="headerlink" title="01背包问题"></a><strong>01背包问题</strong></h2><p>给定两个长度都为N的数组weights和values，weights[i]和values[i]分别代表i号物品的重量和价值。给定一个正数bag，表示一个载重bag的袋子，你装的物品不能超过这个重量。返回你能装下最多的价值是多少。</p>
<figure class="highlight perl"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line">public static <span class="keyword">int</span> process1(<span class="keyword">int</span>[] weights,<span class="keyword">int</span>[] <span class="keyword">values</span>,<span class="keyword">int</span> i,<span class="keyword">int</span> alreadyweight,<span class="keyword">int</span> bag)&#123;</span><br><span class="line">    <span class="keyword">if</span>(alreadyweight &gt; bag)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>( i == weights.length)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> Math.max(</span><br><span class="line">        process1(weights,<span class="keyword">values</span>,i + <span class="number">1</span>,alreadyweight,bag),<span class="regexp">//</span>不要第i号货物</span><br><span class="line">        <span class="keyword">values</span>[i] + process1(weights,<span class="keyword">values</span>,i+<span class="number">1</span>,alreadyweight+ weights[i],bag)); <span class="regexp">//</span>要第i号货物</span><br><span class="line">    )</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>




































































    </div>

    
    
    

      <footer class="post-footer">
          <div class="post-tags">
              <a href="/wang-cheng/tags/%E5%B7%A6%E7%A5%9E/" rel="tag"># 左神</a>
          </div>

        


        
    <div class="post-nav">
      <div class="post-nav-item">
    <a href="/wang-cheng/2022/04/01/%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0-%E4%BA%8C/" rel="prev" title="算法笔记(二)">
      <i class="fa fa-chevron-left"></i> 算法笔记(二)
    </a></div>
      <div class="post-nav-item">
    <a href="/wang-cheng/2022/04/02/%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0-%E5%9B%9B/" rel="next" title="算法笔记(四)">
      算法笔记(四) <i class="fa fa-chevron-right"></i>
    </a></div>
    </div>
      </footer>
    
  </article>
  
  
  



          </div>
          

<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      let activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      let commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>

        </div>
          
  
  <div class="toggle sidebar-toggle">
    <span class="toggle-line toggle-line-first"></span>
    <span class="toggle-line toggle-line-middle"></span>
    <span class="toggle-line toggle-line-last"></span>
  </div>

  <aside class="sidebar">
    <div class="sidebar-inner">

      <ul class="sidebar-nav motion-element">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <!--noindex-->
      <div class="post-toc-wrap sidebar-panel">
          <div class="post-toc motion-element"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95"><span class="nav-number">1.</span> <span class="nav-text">贪心算法</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%E5%9C%A8%E7%AC%94%E8%AF%95%E7%9A%84%E6%97%B6%E5%80%99%E7%9A%84%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-number">1.0.1.</span> <span class="nav-text">贪心算法在笔试的时候的解题思路</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#PriorityQueue%E7%9A%84%E4%BD%BF%E7%94%A8"><span class="nav-number">1.1.</span> <span class="nav-text">PriorityQueue的使用</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#N%E7%9A%87%E5%90%8E%E9%97%AE%E9%A2%98"><span class="nav-number">1.2.</span> <span class="nav-text">N皇后问题</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%9A%B4%E5%8A%9B%E9%80%92%E5%BD%92"><span class="nav-number">1.3.</span> <span class="nav-text">暴力递归</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%B1%89%E8%AF%BA%E5%A1%94%E9%97%AE%E9%A2%98"><span class="nav-number">1.3.1.</span> <span class="nav-text">汉诺塔问题</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%89%93%E5%8D%B0%E4%B8%80%E4%B8%AA%E5%AD%97%E4%B8%B2%E7%9A%84%E5%85%A8%E9%83%A8%E5%AD%90%E5%BA%8F%E5%88%97%EF%BC%8C%E5%8C%85%E6%8B%AC%E7%A9%BA%E5%AD%97%E7%AC%A6%E4%B8%B2"><span class="nav-number">1.3.2.</span> <span class="nav-text">打印一个字串的全部子序列，包括空字符串</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%89%93%E5%8D%B0%E4%B8%80%E4%B8%AA%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E5%85%A8%E9%83%A8%E6%8E%92%E5%88%97"><span class="nav-number">1.3.3.</span> <span class="nav-text">打印一个字符串的全部排列</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E7%BA%B8%E7%89%8C%E7%9A%84%E5%85%88%E6%89%8B%E5%90%8E%E6%89%8B%E6%8B%BF%E9%97%AE%E9%A2%98"><span class="nav-number">1.4.</span> <span class="nav-text">纸牌的先手后手拿问题</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E7%BB%99%E4%BD%A0%E4%B8%80%E4%B8%AA%E6%A0%88%EF%BC%8C%E8%AF%B7%E4%BD%A0%E9%80%86%E5%BA%8F%E8%BF%99%E4%B8%AA%E6%A0%88%EF%BC%8C%E4%B8%8D%E8%83%BD%E7%94%B3%E8%AF%B7%E9%A2%9D%E5%A4%96%E7%9A%84%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%EF%BC%8C%E5%8F%AA%E8%83%BD%E4%BD%BF%E7%94%A8%E9%80%92%E5%BD%92%E5%87%BD%E6%95%B0%E3%80%82%E5%A6%82%E4%BD%95%E5%AE%9E%E7%8E%B0%E3%80%82"><span class="nav-number">1.5.</span> <span class="nav-text">给你一个栈，请你逆序这个栈，不能申请额外的数据结构，只能使用递归函数。如何实现。</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#01%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98"><span class="nav-number">1.6.</span> <span class="nav-text">01背包问题</span></a></li></ol></li></ol></div>
      </div>
      <!--/noindex-->

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
  <p class="site-author-name" itemprop="name">王诚</p>
  <div class="site-description" itemprop="description">命运对勇士低语，你无法抵御风暴；勇士低声回应，我就是风暴</div>
</div>
<div class="site-state-wrap motion-element">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/wang-cheng/archives/">
        
          <span class="site-state-item-count">32</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/wang-cheng/tags/">
          
        <span class="site-state-item-count">12</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>



      </div>

    </div>
  </aside>
  <div id="sidebar-dimmer"></div>


      </div>
    </main>

    <footer class="footer">
      <div class="footer-inner">
        

        

<div class="copyright">
  
  &copy; 
  <span itemprop="copyrightYear">2022</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">王诚</span>
</div>
  <div class="powered-by">由 <a href="https://hexo.io/" class="theme-link" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.org/" class="theme-link" rel="noopener" target="_blank">NexT.Gemini</a> 强力驱动
  </div>

        
<div class="busuanzi-count">
  <script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
    <span class="post-meta-item" id="busuanzi_container_site_uv" style="display: none;">
      <span class="post-meta-item-icon">
        <i class="fa fa-user"></i>
      </span>
      <span class="site-uv" title="总访客量">
        <span id="busuanzi_value_site_uv"></span>
      </span>
    </span>
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item" id="busuanzi_container_site_pv" style="display: none;">
      <span class="post-meta-item-icon">
        <i class="fa fa-eye"></i>
      </span>
      <span class="site-pv" title="总访问量">
        <span id="busuanzi_value_site_pv"></span>
      </span>
    </span>
</div>








      </div>
    </footer>
  </div>

  
  <script src="/wang-cheng/lib/anime.min.js"></script>
  <script src="/wang-cheng/lib/velocity/velocity.min.js"></script>
  <script src="/wang-cheng/lib/velocity/velocity.ui.min.js"></script>

<script src="/wang-cheng/js/utils.js"></script>

<script src="/wang-cheng/js/motion.js"></script>


<script src="/wang-cheng/js/schemes/pisces.js"></script>


<script src="/wang-cheng/js/next-boot.js"></script>




  















  

  

  

</body>
</html>
